package Offer.offer2019;

import domain.TreeNode;

/**
 * 树的子结构
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/28
 * @time: 20:01
 */
public class Offer18 {

    public boolean isSubTree(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return false;
        }

        if (root2 == null) {
            return true;
        }

        boolean result = false;

        if (root1.val == root2.val) {
            result =  doesTree1HasTree2(root1, root2);
        }

        if (!result) {
            result = isSubTree(root1.left, root2);
        }

        if (!result) {
            result = isSubTree(root1.right, root2);
        }

        return result;
    }

    private boolean doesTree1HasTree2(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }

        if (root1 == null) {
            return false;
        }

        if (root1.val != root2.val) {
            return false;
        }

        return doesTree1HasTree2(root1.left, root2.left) && doesTree1HasTree2(root1.right, root2.right);
    }
}
